随手回帖让TA成了论文一作，匿名网友解决重要数学问题
网络论坛 4chan 以宅文化闻名，然而一个匿名网友多年前发布的帖子里竟然包含了优雅的数学证明。最近这条证明被重新发现，数学家们对它进行了验算，并在最终的论文中将“4chan 匿名网友”列为第一作者。
图片来源：Pixabay
来源 Quanta Magazine
撰文 Erica Klarreich
编译 戚译引
2011 年 9 月 16 日，一名动漫爱好者在 4chan 上提出了一个数学问题，讨论动画《凉宫春日的忧郁》的观看次序。这部动画的第一季包含时间旅行剧情，最初以非时间线性顺序播出，重播和 DVD 版也都采取了不同的顺序。粉丝们在网上交流最佳的观看顺序，而有位 4chan 网友提问：要想以每一种可能的顺序观看这部剧集，那么播放列表的最短长度是多少？
一小时之内，有匿名网友提交了答案——这不是一个完整的解答，而是所需的最少剧集数量的下界（lower bound）。论证中给出了对于任何数量的剧集的计算方式，并表明对于包含 14 集的《凉宫春日的忧郁》第一季，观众需要至少观看 93,884,313,611 集，才能看到所有可能的顺序。“请检查（证明），看看有没有什么可能的漏洞，”这个匿名网友写道。
七年来，这个证明并未进入数学界的视线——显然当时只有一名专业的数学家看到了它，而且他没有仔细检查。直到上个月，它才迎来了命运的转折点。澳大利亚科幻作家格雷格·伊根（Greg Egan）证明了所需剧集数量的上界（upper bound），重新引发了数学家对这个问题的兴趣，并让 2011 年那个匿名发布的下界证明也得到了关注。这两个证明都被视为重要的研究进展，为解开一个困扰了数学家至少 25 年的问题提供了启发。
数学家们很快验证，伊根的上界和匿名网友计算的下界适用于任何长度的集合。数据可视化公司 Kiln 的一名数学家罗宾·休斯顿（Robin Houston）和马凯特大学（Marquette University）的杰伊·潘通（Jay Pantone）分别独立验证了 4chan 匿名网友的工作。“要验证这个证明是对是错花了不少工夫，”潘通说，因为证明的关键思想并没有得到特别明确的表达。
如今，休斯顿、潘通和弗罗里达大学（University of Florida）的文斯·维特（Vince Vatter）共同发表了一份正式的证明，他们在论文中将“4chan 匿名网友”列为第一作者。
休斯顿说：“如此优雅地证明了一个不为人知的问题，而且还出现在这样一个不太可能的地方，这种情况还真奇怪。”
排列之城
如果一部剧集只有 3 集，那么它有 6 种可能的观看次序：123、132、213、231、312 和 321。你可以把这六种次序连起来，得到一个长度为 18 集的播放列表，其中包含了所有可能的次序，但还有一种更加高效的方式，就是 123121321（共 9 集）。这样的序列包含了一个具备 n 个元素的集合中所有可能的排列（permutation），叫做超排列（superpermutation）。
1993 年，丹尼尔·艾什洛克（Daniel Ashlock）和詹内特·蒂洛森（Jenett Tillotson）发现，如果观察n取不同值的超排列，我们很快会发现其中的规律和阶乘（factorial）有关。阶乘写作 n!，指所有小于或等于 n 的正整数的乘积（例如 4! = 4 × 3 × 2 × 1）。
如果某个剧集只有 1 集，那么最短的超排列的长度就是 1!。对于包含 2 集的剧集，最短的超排列（121）的长度是 2! + 1!。在 3 集的情况下（例如前面的案例），最短的长度为 3! + 2! + 1!；而到了 4 集的时候，最短的序列是123412314231243121342132413214321，序列长度是 4! + 3! + 2! + 1!。超排列的阶乘规律变成了一种经验智慧（尽管没人能证明它适用于所有的 n），并且数学家后来对 n=5 的情形进行了验证。
要体现 5 个元素所有可能的排列，序列的最小长度是 5! + 4! + 3! + 2! + 1! = 153。| 图片来源：Pixabay
直到 2014 年，休斯顿证明这条规律在 n=6 时不成立，让数学家吓了一跳。按照阶乘计算，以每一种可能的顺序观看6部剧集，播放列表至少包含 873 集，然而休斯顿找到了一种办法，让它变成了 872 集。而且，由于有一种简单的方式能够将 n 个元素的较短超排列转换成 n+1 个元素的较短超排列，休斯顿的案例说明，阶乘规律对所有 n>6 的情况都不再适用。
休斯顿的工作将超排列问题进行了重构，将其转换成著名的旅行推销员问题（traveling salesman problem），即寻找穿过一系列城市的最短路线。具体而言，超排列与“不对称”旅行推销员问题有关，即连接两个城市的路线需要收费（不同方向收费可能不同），此时推销员的目标是找到穿过所有城市的最便宜的路线。
这个转换过程很简单。假设每种排列都是一座“城市”，再想象连接两种排列的路线。在超排列问题中，我们希望能够得到能够包含所有可能排列的最短的序列，所以我们的目标是在各个排列之间“旅行”，每次旅行都会对开始的排列加上几个字节。因此，定义每条路线的“路费”为需要在上一个排列后面添加的字节数，例如在 n=3 的情况下，从 231 到 312 花费 1 美元，因为我们只要在 231 后面加上一个 2，就能得到 312。按照这样的设定，连接城市之间开支最少的路线就对应了最短的超排列。
图片来源：Lucy Reading-Ikkanda/Quanta Magazine / 翻译：科研圈
这种转换意味着休斯顿可以将解答旅行推销员问题的算法拿来解决超排列问题。旅行推销员问题是一个著名的 NP 困难问题，也就是说没有一种有效的算法能够适用于所有的情况。但是，有的算法可以高效地解决一部分情况下的问题，而另一些算法能够计算出足够接近的答案。休斯顿采用了后者，计算出了那个长度为 872 的超排列。
由于他算出的只是一个近似解，这也许并非最好的超排列。潘通说，数学家们正在运行一次大型计算机搜索，寻找 6 个元素的最短超排列。他说：“我们知道这次搜索将在有限的时间内完成，但是我们不知道那会是一星期还是一百万年。没有进度条。”
错误的次序
当休斯顿完成那项工作的时候，那篇匿名发布的 4chan 帖子已经在互联网的角落里安静地待了近三年。其实在帖子发布几天后，蒙特埃里森大学（Mount Allison University）的一名数学家纳撒尼尔·约翰斯顿（Nathaniel Johnston）就在另一个网站上看到了它的副本——他并不是沉迷动漫，只是在谷歌上搜索超排列相关的内容。
约翰斯顿读了那条证明，觉得它看起来还靠谱，但他并没有投入太多的精力去自习检查。当时数学家认为对超排列的阶乘计算很可能是对的，而当你自认为知道了一个问题的准确答案，那么它的下界看起来就没什么意思了。换言之，超排列的研究进程也没有遵守它的播放次序。
约翰斯顿后来在一两个网站上看到了这个下界，他说：“我不认为有谁留意到这个证明。”
然后，到了今年的 9 月 26 日，加利福尼亚大学河滨分校（University of California, Riverside）的数学家约翰·巴耶兹（John Baez）在推特上发布了休斯顿 2014 年的发现，用来举例介绍本以为显而易见、实际上并不正确的数学规律。这条推特引起了科幻作家伊根的注意。伊根在几十年前就读于数学系，后来他成了一名屡屡获奖的科幻小说家（有趣的是，他在 1994 年的突破性作品就叫《置换城市》（Permutation City）。）伊根在邮件中写道：“我对数学的兴趣从未减退。”
伊根想知道能否构建一个比休斯顿的答案更短的超排列。他阅读了相关文献，了解如何通过超排列网络构建较短路线，在几个星期后就找到了他需要的东西。在一两天内，他算出了 n 个元素的最短超排列的长度上界，就是 n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3。它和原先的阶乘公式相似，但去掉了很多项。
休斯顿说：“这绝对打败了先前的上界。”
与此同时，4chan 的匿名帖子计算的下界和新的上界极其接近，就是 n! + (n – 1)! + (n – 2)! + n – 3。当伊根的答案被公之于众之后，约翰斯顿提醒其他的数学家关注匿名帖子中的证明，而休斯顿和潘通很快验证它是正确的。和休斯顿的工作一样，新的下界和上界都通过旅行推销员问题实现了超排列：下界体现了必须经过的路费大于 1 美元的路线的最小数量，而上界计算出仅从路费为 1 美元和 2 美元的路线经过的方式，适用于不同的 n 值。
研究人员目前正在努力将上界和下界相结合，找出超排列问题的唯一解。巴耶兹预言：“也许人们终于要对这个问题盖棺定论了。现在的形势不错。”
而对于凉宫春日的粉丝来说，伊根的计算给出了在仅仅 93,924,230,411 集中看完第一季所有可能顺序的实用方式。粉丝们可以马上开始努力观看，或者再等等看数学家能不能把这个数字缩小一点。不过匿名网友计算的下界说明，最终波动范围不太可能超过 4 千万集。
本文来自微信公众号“科研圈”。如需转载，请在“科研圈”后台回复“转载”，或通过公众号菜单与我们取得联系。原始文章请点击“阅读原文”。
阅读论文解读及推荐
点击👉关注领研网论文频道。
▽ 精彩回顾 ▽